Print rendering systems need to composite and blend multiple graphic objects with different opacities to produce final print-ready page data. Printing systems need to composite and blend objects in a timely manner to meet the page rate of the output printing engine. As the resolution and speed of print engines increases, new methods for compositing and blending of graphics objects are required to keep up with the output print engine.
Traditional Porter and Duff compositing requires that all pixels of the same X,Y location on a page contributing to a result for that location be processed in order up the z-stack (the z-ordered list of image layers that contribute to the colour of a pixel), with the page background processed first, and the top-most layer processed last. This ordering is required, as that is the order in which objects are placed on the page by the input PDL file, and the order cannot be changed as Porter and Duff compositing is not commutative for every blend mode. The term “commutative” can be understood by reference to the arithmetic operation of addition which is commutative over a set of real numbers, meaning that a+b=b+a for all real numbers a and b. This constraint on traditional Porter and Duff compositing can lead to unnecessary processing, because if a layer other than the bottom layer is fully opaque, then there is no need to process the layers below. Since the layers are processed from the bottom up, however, a fully opaque layer is not detected until all layers beneath it have already been processed.
Traditional renderers, both edge based and “painters algorithm” based, have used different methods to mitigate the above. PDL groups of objects in the z-stack can sometimes be rendered separately for some blend modes. The printed page can be broken into bands or tiles, and these can be rendered in parallel. However, this approach is poorly suited to massively parallel systems (such as Graphic Processing Units or GPUs), as the segmentation of the work is coarse.
For an edge based renderer, one solution to the opaque efficiency issue with bottom-up compositing is to modify the bottom-up algorithm to be a two pass algorithm. An initial, fast, top-down scan of the z-stack of layers is used to locate the top-most fully opaque layer by examining the compositing data of each layer identified previously. The bottom-up compositing process is then done in a second pass, and starts from the top-most fully opaque layer. While this partially solves the above issue of detecting a fully opaque layer, the method only detects an opaque layer on a per-object basis. Therefore, if an object has a mixture of opaque and transparent pixels, e.g. an image mask, then the whole object is marked as transparent and compositing would be performed for all pixels of the object, which is a computationally intensive operation.
Some prior-art methods are able to overcome the serial nature of compositing and the opaque layer efficiency issue by restricting compositing operations to the associative Porter and Duff compositing operations and thereby allowing a final compositing output for each group in the z-stack to be determined independently from an output of any other group in the z-stack. The associative property of an operation states that you can perform the operation regardless of how the numbers are grouped. By ‘grouped’ we mean ‘how you use parenthesis’. In other words, if you are adding or multiplying it does not matter where you put the parenthesis. For example, if a+(b+c)=(a+b)+c for any a, b and c in a set, then operation “+” is associative.
Given that the prior-art methods are restricted to associative compositing operations, i.e. are not applicable to non-associative compositing operations, they would provide an incorrect compositing output if there are non-associative compositing operations in a z-stack of layers. Modern printing systems, however, must cope with a variety of blend modes, including non-associative compositing operations. Therefore, there is a need for a system and method for parallelising compositing of a plurality layers in accordance with general, including non-associative, compositing operations.